package com.example.algorithm.two_dimensional_array;

// 这题演示的是，顺指针旋转二维数组。
// 二维数组为什么可以旋转，因为，二维数组我们如果把它当做向量的话，一个二维数组可以写成一个矩阵。所以，我们说的这个顺时针旋转90度，是针对矩阵这个图形来说的。
// 旋转技巧的话，如果不优化，那就是把遍历n*n次，把所有的元素都按照a[i][j] = a[n-1-j][i]的规律来交换位置。
// 如果优化的话，那就元素4个为一组的换，具体内部细节是怎样减少重复替换和哪些重复部分被优化了，暂时不研究，记住这样换就好。
// 记得要参考面试表格里面的图解。
public class ClockwiseRotationBy90Degree {

    public static void main(String[] args) {
        int[][] matrix = {
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}
        };
        // 旋转之后，要变成下面这样就好。也就是从图形上来看，是顺时针旋转了90度。
        // matrix = {
        //                {3, 6, 9},
        //                {2, 5, 8},
        //                {1, 4, 7}
        //  };
        // 这个可能看起来有点奇怪，感觉是逆时针旋转了90度，其实不是这样的。始终记住，我们向量一般来说是竖着写的，也就是默认是写列向量。
        // 那么，原始数组，写成向量或者说矩阵的形式，就是：
        // 1  4  7
        // 2  5  8
        // 3  6  9
        // 旋转之后数组呢，写成列向量或者说矩阵的形式，就是：
        // 3  2  1
        // 6  5  4
        // 9  8  7
        // 所以，比较这两个矩阵，看看，确实是顺时针旋转了。因为列向量写成matrix定义中的那种类似行向量的格式的时候，其实效果是转置,转置的话，方向看起来是不一样的。
        System.out.println("旋转前：");
        for (int[] arr : matrix) {
            for (int item : arr) {
                System.out.println(item);
            }
        }
        retate(matrix);

        System.out.println("旋转后：");
        for (int[] arr : matrix) {
            for (int item : arr) {
                System.out.println(item);
            }
        }
    }

    // 换位置的规律是：a[i][j] = a[n-1-j][i]。
    // 不管等于多少阶，都满足这个规律。
    // 简单地记忆这个规律就是，首先先把行、列交换，然后，转动后的数组，它的行是取数组长度的补集合。长度是n，但是从长度换算到索引，就是n-1，然后减去j，我把这叫做取补集。
    // 但是，下面这个优化，是做了一些算法上的优化的。不过我没看太懂。
    public static void retate(int[][] matrix) {

        // 外层数组的长度。5
        int n = matrix.length;

        // i是用来遍历行的。
        // i = 0是因为，索引是从开始。i<n/2而不是i<= i/2，也正是因为，索引是从0开始算的。
        // 至于为什么是n/2呢，比如行数是偶数，如6，那么，事实上，在行上面的遍历，我们只有遍历前三行。如果行数是奇数，那么，在行上的遍历，我们也只用遍历前面三行，第四行的那个元素一般是正中间的元素，它的位置不变。
        for (int i = 0; i < n / 2; i++) {
            // j是用来遍历列的。
            // 列的范围：
            // 它的头，会每轮递增。具体体现在j++这句代码上。
            // 它的尾，会每轮递减，具体体现在i++这句代码上，而，j的尾巴，是由n - 1 - i，i是每轮递增的，所以，j的尾巴，自然就是每轮递减的。
            // j的初始值的话，头是j=0，尾是j=n-1-0=n-1。确定了j的头尾的初始值，然后弄清楚头尾的递增递减特点，其实就不会犯错了。
            for (int j = i; j < n - 1 - i; j++) {
                int temp = matrix[i][j];
                // 上面的两个for只是确定i、j要交换的范围。其实是处于优化算法的考虑，如果不处于优化算法的考虑，i、j的遍历范围，都为[0， n-1]。并且，特别需要注意的是，不优化的时候，并不是在原始的数组上做交换，而是把一个原始数组的元素，誊写到空数组的某个特定位置。不优化是两个数组之间的誊写而不是交换，而优化后是在原数组上做交换，知道这点是特别重要的。
                // 而下面这个是优化后的做法，它是在原数组上进行的，采用的是四个一组，然后按照某种方式把值换到指定的位置。大体它依据了如果一个元素的原始位置是[i][j]那么它在转动后的数组中的位置肯定是a[n-1-j][i]这个规律，但是，中间需要一些额外的推导过程。
                // 每次是四个数字要交换，是在原来的数组上交换，必须要额外定义一个临时的空杯子。交换都是这样的，需要空杯子。tmp变量，就是那个空杯子。
                // 为了便于称呼，我们假设一个四边形的四个顶点从左上开始数，依次我把它叫做A、B、C、D
                // 那么，此刻，A点的坐标就是matrix[i][j]，这个是必然的，因为没有一组四个点中的其他三个点能够比他更靠左，更加靠上了。
                // A点转动之后，要到B点，那么，B点的坐标满足那个基本规律，所以，B点的坐标是matrix[j][n-1-i]
                // B点转动之后，会到C点，所以，B与C之间，也满足那个基本规律，那么，知道B点，C点就是matrix[n-1-i][n-1-j]
                // 同样地，知道C点，就可以知道D点，因为C与D之间满足那个基本规律，所以D点就是matrix[n-1-j][n-1-(n-1-i)]简化一下就是matrix[n-1-j][i]
                // 任何一个这样的一组四个点，四个位置上的点都满足这样的关系。所以，按照规则交换就行：
                // 先把A位置上的值取出备份，放入temp
                // 然后D位置上的值赋值给A，C位置上的值赋值给D，B位置上的值赋值给C、A位置上的值(temp)赋值给B
                matrix[i][j] = matrix[n - 1 - i][i];
                matrix[n - 1 - i][i] = matrix[n - 1 - i][n - 1 - j];
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = temp;
            }
        }
    }
}
